package algorithm.niuke;

import java.util.Arrays;

public class 带因子的二叉树 {
    boolean log = false;
    public int numFactoredBinaryTrees(int[] A) {
        int len = A.length;
        int[] nums = A;
        long[] count = new long[len];
        Arrays.sort(nums);
        final long MOD = 1000000007;
        for(int i=0;i<len;i++){
            count[i] = 1;
            for(int j=i-1;j>=0;j--){
                int mod = nums[i] % nums[j];
                if(mod == 0){
                    int num = nums[i] / nums[j];
                    for(int k=0;k<i;k++){
                        if(nums[k] == num){
                            long temp = count[k] * count[j];
                            count[i] += temp;
                            count[i] %= MOD;
                        }
                    }
                }
            }
        }
        long total = 0;
        for(int i=0;i<len;i++){
            total += count[i];
            total %= MOD;
        }
        total %= MOD;
        return (int)(total);
    }

    public static void main(String[] args) {
        int[] nums = { 45, 42, 2, 18, 23, 1170, 12, 41, 40, 9, 47, 24, 33, 28, 10, 32, 29, 17, 46, 11, 759, 37, 6, 26,
                21, 49, 31, 14, 19, 8, 13, 7, 27, 22, 3 };
        带因子的二叉树 run = new 带因子的二叉树();
        System.out.println(run.numFactoredBinaryTrees(nums));
    }
}
